use std::{cell::RefCell, fmt, rc::Rc};

#[derive(Clone)]
pub struct BTreeNode<T: PartialEq + Copy + PartialOrd + Default + fmt::Display> {
    n: RefCell<usize>,
    key: RefCell<Vec<RefCell<T>>>,
    leaf: RefCell<bool>,
    children: RefCell<Vec<RefCell<Rc<BTreeNode<T>>>>>,
}

impl<T: PartialEq + Copy + PartialOrd + Default + fmt::Display> BTreeNode<T> {
    pub fn build() -> BTreeNode<T> {
        BTreeNode {
            n: RefCell::new(0),
            key: RefCell::new(Vec::<RefCell<T>>::new()),
            leaf: RefCell::new(true),
            children: RefCell::new(Vec::<RefCell<Rc<BTreeNode<T>>>>::new()),
        }
    }
    pub fn get_n(&self) -> usize {
        unsafe { *(self.n.as_ptr()) }
    }
    pub fn set_n(&self, v: usize) {
        *(self.n.borrow_mut()) = v;
    }
    pub fn get_key(&self) -> &Vec<RefCell<T>> {
        unsafe { &*(self.key.as_ptr()) }
    }
    pub fn get_children(&self) -> &Vec<RefCell<Rc<BTreeNode<T>>>> {
        unsafe { &*(self.children.as_ptr()) }
    }
    pub fn get_key_i(&self, i: usize) -> T {
        unsafe { *(self.get_key()[i].as_ptr()).clone() }
    }
    pub fn set_key_i(&self, i: usize, v: T) {
        *(self.get_key()[i].borrow_mut()) = v;
    }
    pub fn get_leaf(&self) -> bool {
        unsafe { *(self.leaf.as_ptr()) }
    }
    pub fn set_leaf(&self, b: bool) {
        *(self.leaf.borrow_mut()) = b;
    }
    pub fn get_chlid_i(&self, i: usize) -> Rc<BTreeNode<T>> {
        unsafe { Rc::clone(&(*(self.get_children()[i].as_ptr()))) }
    }
    pub fn set_child_i(&self, i: usize, child: Rc<BTreeNode<T>>) {
        *(self.get_children()[i].borrow_mut()) = child;
    }
    pub fn key_push(&self, k: T) {
        let mut temp = self.key.borrow_mut();
        (*temp).push(RefCell::new(k));
        self.set_n(self.get_n() + 1);
    }
    pub fn key_pop(&self) {
        let mut temp = self.key.borrow_mut();
        (*temp).pop();
        self.set_n(self.get_n() - 1);
    }
    pub fn children_push(&self, node: Rc<BTreeNode<T>>) {
        self.children
            .borrow_mut()
            .push(RefCell::new(Rc::clone(&node)));
    }
    pub fn children_pop(&self) {
        self.children.borrow_mut().pop();
    }
    pub fn delete_key_i(&self, i: usize) {
        self.key.borrow_mut().remove(i);
        self.set_n(self.get_n() - 1);
    }
    pub fn delete_child_i(&self, i: usize) {
        self.children.borrow_mut().remove(i);
    }
    pub fn key_conclude(&self, k: T) -> (bool, usize) {
        let mut i: usize = 0;
        while i < self.get_n() && self.get_key_i(i) < k {
            i += 1;
        }
        if i < self.get_n() && self.get_key_i(i) == k {
            (true, i)
        } else {
            (false, i)
        }
    }
    pub fn key_insert(&self, k: T, i: usize) {
        self.key.borrow_mut().insert(i, RefCell::new(k));
        self.set_n(self.get_n() + 1);
    }
    pub fn child_insert(&self, v: Rc<BTreeNode<T>>, i: usize) {
        self.children
            .borrow_mut()
            .insert(i, RefCell::new(Rc::clone(&v)));
    }
}

impl<T: PartialEq + Copy + PartialOrd + Default + fmt::Display> fmt::Display for BTreeNode<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        for i in 0..self.get_n() {
            print!("{} --- ", self.get_key_i(i));
        }
        write!(f, "| ")
    }
}

pub struct BTree<T: PartialEq + Copy + PartialOrd + Default + fmt::Display> {
    root: Option<RefCell<Rc<BTreeNode<T>>>>,
    t: usize,
}

impl<T: PartialEq + Copy + PartialOrd + Default + fmt::Display> fmt::Display for BTree<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if let Some(root) = self.get_root() {
            let mut node_list: Vec<Rc<BTreeNode<T>>> = Vec::new();
            let mut node_list_temp: Vec<Rc<BTreeNode<T>>> = Vec::new();
            node_list.push(Rc::clone(&root));
            while !node_list.is_empty() {
                node_list_temp.clear();
                for node in node_list.iter() {
                    print!("{}", node);
                    if !node.get_leaf() {
                        for i in 0..=node.get_n() {
                            node_list_temp.push(node.get_chlid_i(i));
                        }
                    }
                }
                println!("\n");
                node_list = node_list_temp.clone();
            }
            write!(f, "")
        } else {
            write!(f, "Empty!")
        }
    }
}

impl<T: PartialEq + Copy + PartialOrd + Default + fmt::Display> BTree<T> {
    pub fn get_root(&self) -> Option<Rc<BTreeNode<T>>> {
        if let Some(v) = self.root.as_ref() {
            unsafe { Some(Rc::clone(&(*(v.as_ptr())))) }
        } else {
            None
        }
    }
    pub fn set_root(&self, r: Rc<BTreeNode<T>>) {
        if let Some(v) = self.root.as_ref() {
            *(v.borrow_mut()) = r;
        }
    }
    pub fn build(n: usize) -> BTree<T> {
        let v = BTreeNode::build();
        BTree {
            root: Some(RefCell::new(Rc::new(v))),
            t: n,
        }
    }
    pub fn b_tree_search(&self, x: Rc<BTreeNode<T>>, k: T) -> (Rc<BTreeNode<T>>, usize) {
        let mut i: usize = 0;
        while i < x.get_n() && k > x.get_key_i(i) {
            i += 1;
        }
        if i < x.get_n() && k == x.get_key_i(i) {
            return (Rc::clone(&x), i);
        } else {
            return self.b_tree_search(x.get_chlid_i(i), k);
        }
    }
    pub fn b_tree_split_child(&self, x: Rc<BTreeNode<T>>, i: usize) {
        let z: BTreeNode<T> = BTreeNode::build();
        let y = x.get_chlid_i(i);
        z.set_leaf(y.get_leaf());
        for j in 0..(self.t - 1) {
            z.key_push(y.get_key_i(j + self.t));
        }
        if !y.get_leaf() {
            for j in 0..=(self.t - 1) {
                z.children_push(Rc::clone(&(y.get_chlid_i(j + self.t))));
            }
        }
        x.child_insert(Rc::new(z), i + 1);
        x.key_insert(y.get_key_i(self.t - 1), i);
        for _ in (self.t - 1)..(y.get_n()) {
            y.key_pop();
        }
        if !y.get_leaf() {
            for _ in 0..self.t {
                y.children_pop();
            }
        }
    }
    pub fn b_tree_insert_nonfull(&self, x: Rc<BTreeNode<T>>, k: T) {
        let mut i = x.get_n();
        if x.get_leaf() {
            x.key_push(k);
            while i >= 1 && k < x.get_key_i(i - 1) {
                x.set_key_i(i, x.get_key_i(i - 1));
                i -= 1;
            }
            x.set_key_i(i, k);
        } else {
            let mut i = i - 1;
            while i >= 1 && k < x.get_key_i(i) {
                i -= 1;
            }
            if !(i == 0 && k < x.get_key_i(i)) {
                i += 1;
            }
            if x.get_chlid_i(i).get_n() == self.t * 2 - 1 {
                self.b_tree_split_child(Rc::clone(&x), i);
                if k > x.get_key_i(i) {
                    i += 1;
                }
            }
            self.b_tree_insert_nonfull(x.get_chlid_i(i), k);
        }
    }
    pub fn b_tree_insert(&self, k: T) {
        if let Some(r) = self.get_root() {
            if r.get_n() == self.t * 2 - 1 {
                let s: BTreeNode<T> = BTreeNode::build();
                s.set_leaf(false);
                s.children_push(Rc::clone(&r));
                let s_rc = Rc::new(s);
                self.set_root(Rc::clone(&s_rc));
                self.b_tree_split_child(Rc::clone(&s_rc), 0);
                self.b_tree_insert_nonfull(Rc::clone(&s_rc), k);
            } else {
                self.b_tree_insert_nonfull(Rc::clone(&r), k);
            }
        } else {
            let s: BTreeNode<T> = BTreeNode::build();
            s.key_push(k);
            self.set_root(Rc::new(s));
        }
    }
    pub fn b_tree_delete_execute(&self, x: Rc<BTreeNode<T>>, i: usize) {
        if x.get_leaf() {
            x.delete_key_i(i);
        } else {
            let x_left_child = x.get_chlid_i(i);
            if x_left_child.get_n() >= self.t {
                let m = x_left_child.get_n() - 1;
                let k = x_left_child.get_key_i(m);
                x.set_key_i(i, k);
                self.b_tree_delete_execute(x_left_child, m);
            } else {
                let x_right_child = x.get_chlid_i(i + 1);
                let m = x_left_child.get_n();
                if x_right_child.get_n() >= self.t {
                    let k = x_right_child.get_key_i(0);
                    x.set_key_i(i, k);
                    self.b_tree_delete_execute(x_right_child, 0);
                } else {
                    x_left_child.key_push(x.get_key_i(i));
                    for j in 0..x_right_child.get_n() {
                        x_left_child.key_push(x_right_child.get_key_i(j));
                    }
                    if !x_right_child.get_leaf() {
                        for j in 0..=(x_right_child.get_n()) {
                            x_left_child.children_push(x_right_child.get_chlid_i(j));
                        }
                    }
                    x.delete_key_i(i);
                    x.delete_child_i(i + 1);
                    self.b_tree_delete_execute(x_left_child, m);
                }
            }
        }
    }
    pub fn b_tree_delete(&self, k: T) {
        if let Some(root) = self.get_root() {
            let (mut cond, mut i) = root.key_conclude(k);
            println!("删除节点 {}", k);
            println!("寻找删除节点的路径");
            print!("{}({}) --> ", i, cond);
            if cond {
                self.b_tree_delete_execute(Rc::clone(&root), i);
                println!("Done\n");
            } else {
                let mut x = Rc::clone(&root);
                let mut x_child = root.get_chlid_i(i);
                let mut j = i;
                let tuple = x_child.key_conclude(k);
                cond = tuple.0;
                i = tuple.1;
                print!("{}({}) --> ", i, cond);
                while !cond {
                    x = Rc::clone(&x_child);
                    x_child = x_child.get_chlid_i(i);
                    j = i;
                    let tuple = x_child.key_conclude(k);
                    cond = tuple.0;
                    i = tuple.1;
                    print!("{}({}) --> ", i, cond);
                }
                println!("Done");
                println!("调整");
                if x_child.get_n() < self.t {
                    if j != 0 && x.get_chlid_i(j - 1).get_n() >= self.t {
                        let x_child_left = x.get_chlid_i(j - 1);
                        x_child.key_insert(x.get_key_i(j - 1), 0);
                        let x_child_left_n = x_child_left.get_n();
                        x_child.child_insert(x_child_left.get_chlid_i(x_child_left_n - 1), 0);
                        x.set_key_i(j - 1, x_child_left.get_key_i(x_child_left_n - 1));
                        x_child_left.delete_key_i(x_child_left_n - 1);
                        x_child_left.delete_child_i(x_child_left_n - 1);
                    } else if j != x.get_n() && x.get_chlid_i(j + 1).get_n() >= self.t {
                        let x_child_right = x.get_chlid_i(j + 1);
                        x_child.key_push(x.get_key_i(j));
                        x_child.children_push(x_child_right.get_chlid_i(0));
                        x.set_key_i(j, x_child_right.get_key_i(0));
                        x_child_right.delete_key_i(0);
                        x_child_right.delete_child_i(0);
                    } else {
                        if j != x.get_n() {
                            x_child.key_push(x.get_key_i(0));
                            let x_child_right = x.get_chlid_i(1);
                            for m in 0..x_child_right.get_n() {
                                x_child.key_push(x_child_right.get_key_i(m));
                            }
                            for m in 0..=(x_child_right.get_n()) {
                                x_child.children_push(x_child_right.get_chlid_i(m));
                            }
                            x.delete_key_i(0);
                            x.delete_child_i(1);
                        } else {
                            x_child.key_insert(x.get_key_i(j - 1), 0);
                            let x_child_left = x.get_chlid_i(j - 1);
                            for m in (0..x_child_left.get_n()).rev() {
                                x_child.key_insert(x_child_left.get_key_i(m), 0);
                            }
                            for m in (0..=x_child_left.get_n()).rev() {
                                x_child.child_insert(x_child_left.get_chlid_i(m), 0);
                            }
                            x.delete_key_i(j - 1);
                            x.delete_child_i(j - 1);
                        }
                    }
                }
                if root.get_n() == 0 {
                    self.set_root(Rc::clone(&root.get_chlid_i(0)));
                }
                println!("{}", self);
                println!("删除");
                let tuple = x_child.key_conclude(k);
                self.b_tree_delete_execute(Rc::clone(&x_child), tuple.1);
            }
        }
    }
}

/*
   let btree:BTree<i32> = BTree::build(2);
   btree.b_tree_insert(6);
   btree.b_tree_insert(34);
   btree.b_tree_insert(12);
   btree.b_tree_insert(46);
   btree.b_tree_insert(3);
   btree.b_tree_insert(1);
   btree.b_tree_insert(25);
   btree.b_tree_insert(2);
   btree.b_tree_insert(100);
   btree.b_tree_insert(7);
   println!("{}", btree);
   btree.b_tree_delete(3);
   println!("{}", btree);
   btree.b_tree_delete(12);
   println!("{}", btree);
   btree.b_tree_delete(7);
   println!("{}", btree);
*/
